package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.HashMap;
import java.util.List;

/**
 * https://leetcode.cn/problems/implement-trie-prefix-tree/?envType=study-plan-v2&envId=top-100-liked
 * 参考以往，了解过程
 *
 * @author yulongTian
 * @create 2024-06-28 16:07
 */
public class Test54 {
    public static void main(String[] args) {

    }

    class TrieTreeNode {
        //节点值
        private Character value;
        //该节点下属系列节点
        private HashMap<Character, TrieTreeNode> nexts;
        //该节点是否为某一个单词的结尾标志
        private boolean endNodeFlag;

        //初始化
        public TrieTreeNode(Character value) {
            this.value = value;
            nexts = new HashMap<>();
            this.endNodeFlag = false;
        }

        //getter和setter
        public HashMap<Character, TrieTreeNode> getNexts() {
            return nexts;
        }

        public boolean isEndNodeFlag() {
            return endNodeFlag;
        }

        public void setEndNodeFlag(boolean endNodeFlag) {
            this.endNodeFlag = endNodeFlag;
        }
    }

    class Trie {
        //根节点值
        Character rootValue = '$';
        //根节点
        TrieTreeNode root;

        public Trie() {
            root = new TrieTreeNode(rootValue);
        }

        public void insert(String word) {
            TrieTreeNode nowNode = this.root;
            char[] chars = word.toCharArray();
            for (char c : chars) {
                if (!nowNode.getNexts().containsKey(c)) {
                    TrieTreeNode newNode = new TrieTreeNode(c);
                    nowNode.getNexts().put(c, newNode);
                }
                nowNode = nowNode.getNexts().get(c);
            }
            nowNode.setEndNodeFlag(true);
        }

        public boolean search(String word) {
            TrieTreeNode nowNode = this.root;
            char[] chs = word.toCharArray();
            for (char c : chs) {
                if (nowNode.getNexts().containsKey(c)) {
                    nowNode = nowNode.getNexts().get(c);
                } else {
                    return false;
                }
            }
            return nowNode.isEndNodeFlag();
        }

        public boolean startsWith(String prefix) {
            TrieTreeNode nowNode = this.root;
            char[] chs = prefix.toCharArray();
            for (char c : chs) {
                if (nowNode.getNexts().containsKey(c)) {
                    nowNode = nowNode.getNexts().get(c);
                } else {
                    return false;
                }
            }
            return true;
        }
    }

}
